import java.util.*;

class Solution114 {
    public String alienOrder(String[] words) {

        int len  = words.length ;
        if(len <= 1)  return words[0] ;

        // 记录入度指向
        int[] rudu = new int[26] ;
        Set<Character> hash = new LinkedHashSet<>() ;
        Map<Character,Set<Character>> map = new HashMap<>() ;
        for(int i = 0 ;i < len  ; i ++){
            for(int j= i+1 ; j < len ;  j ++){
                String a = words[i] , b = words[j] ;
                int min = a.length() < b.length() ? a.length() : b.length() ;
                int z = 0 ;
                for(; z < min ; z++){
                    char x = a.charAt(z) , y = b.charAt(z) ;
                    hash.add(x) ;
                    hash.add(y) ;
                    if(x != y ){
                        if(map.containsKey(x)){
                            if(!map.get(x).contains(y)){
                                map.get(x).add(y) ;
                                rudu[y-'a'] ++ ;
                            }
                        }else{
                            map.put(x , new LinkedHashSet<Character>()) ;
                            map.get(x).add(y) ;
                            rudu[y-'a'] ++ ;
                        }
                        break ;
                    }
                }
                if(a.length() > b.length() && z==min && a.charAt(z-1) == b.charAt(z-1)){
                    return "" ;
                }
                while(z <a.length() || z < b.length() ){
                    if(z < a.length()) {
                        if(!hash.contains(a.charAt(z))){
                            hash.add(a.charAt(z)) ;
                        }
                    }
                    if(z < b.length()){
                        if(!hash.contains(b.charAt(z))){
                            hash.add(b.charAt(z)) ;
                        }
                    }
                    z++ ;
                }

            }
        }
        Queue<Character> queue = new LinkedList<>() ;
        StringBuilder strbu = new StringBuilder() ;
        for(char ch : hash){
            if(rudu[ch-'a'] == 0){
                queue.add(ch) ;
            }
        }


        while(!queue.isEmpty()){
            char ch = queue.poll() ;
            Set<Character> li = map.get(ch) ;
            strbu.append(ch) ;
            if(li != null)
                for(char ret : li){
                    rudu[ret -'a'] -- ;
                    if(rudu[ret-'a'] == 0){
                        queue.add(ret) ;
                    }
                }
        }
        if(strbu.length() < hash.size()){
            return "" ;
        }
        return strbu.toString() ;

    }
}